- Chandra Chekuri, Aleksander Bjørn Grodt Christiansen, Jacob Holm, Ivor van der Hoog, Kent Quanrud, Eva Rotenberg, Chris Schwiegelshohn:
Adaptive Out-Orientations with Applications. CoRR abs/2310.18146 (2023) - Mikkel Abrahamsen, Joakim Blikstad, André Nusser, Hanwen Zhang:
Minimum Star Partitions of Simple Polygons in Polynomial Time. CoRR abs/2311.10631 (2023) - Thomas D. Ahle, Sahar Karimi, Peter Tak Peter Tang:
Favour: FAst Variance Operator for Uncertainty Rating. CoRR abs/2311.13036 (2023) - Anders Aamand, Justin Y. Chen, Huy Lê Nguyen, Sandeep Silwal, Ali Vakilian:
Improved Frequency Estimation Algorithms with and without Predictions. CoRR abs/2312.07535 (2023) - Mikkel Abrahamsen, Sarita de Berg, Lucas Meijer, André Nusser, Leonidas Theocharous:
Clustering with Few Disks to Minimize the Sum of Radii. CoRR abs/2312.08803 (2023) - Ivan Damgård, Hannah Keller, Boel Nelson, Claudio Orlandi, Rasmus Pagh:
Differentially Private Selection from Secure Distributed Computing. IACR Cryptol. ePrint Arch. 2023: 894 (2023) - 2022
- Martin Aumüller, Sariel Har-Peled, Sepideh Mahabadi, Rasmus Pagh, Francesco Silvestri:
Sampling near neighbors in search for fairness. Commun. ACM 65(8): 83-90 (2022) - Mikkel Abrahamsen, Anna Adamaszek, Tillmann Miltzow:
The Art Gallery Problem is ∃ℝ-complete. J. ACM 69(1): 4:1-4:70 (2022) - Jean Cardinal, Aurélien Ooms:
Algorithms for approximate sparse regression and nearest induced hulls. J. Comput. Geom. 13(1) (2022) - Christian Janos Lebeda, Martin Aumüller, Rasmus Pagh:
Representing Sparse Vectors with Differential Privacy, Low Error, Optimal Space, and Fast Access. J. Priv. Confidentiality 12(2) (2022) - Anders Aamand, Debarati Das, Evangelos Kipouridis, Jakob Bæk Tejs Knudsen, Peter M. R. Rasmussen, Mikkel Thorup:
No Repetition: Fast and Reliable Sampling with Highly Concentrated Hashing. Proc. VLDB Endow. 15(13): 3989-4001 (2022) - Arkadev Chattopadhyay, Marek Cygan, Noga Ron-Zewi, Christian Wulff-Nilsen:
Special Section on the Fifty-Second Annual ACM Symposium on the Theory of Computing (STOC 2020). SIAM J. Comput. 51(3): 20- (2022) - Holger Dell, John Lapinskas, Kitty Meeks:
Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle. SIAM J. Comput. 51(4): 849-899 (2022) - Rasmus Pagh:
Technical Perspective: Relative Error Streaming Quantiles. SIGMOD Rec. 51(1): 68 (2022) - Stephen Alstrup, Søren Dahlgaard, Arnold Filtser, Morten Stöckel, Christian Wulff-Nilsen:
Constructing light spanners deterministically in near-linear time. Theor. Comput. Sci. 907: 82-112 (2022) - Martin Aumüller, Sariel Har-Peled, Sepideh Mahabadi, Rasmus Pagh, Francesco Silvestri:
Sampling a Near Neighbor in High Dimensions - Who is the Fairest of Them All? ACM Trans. Database Syst. 47(1): 4:1-4:40 (2022) - Matti Karppa, Martin Aumüller, Rasmus Pagh:
DEANN: Speeding up Kernel-Density Estimation using Approximate Nearest Neighbor Search. AISTATS 2022: 3108-3137 - Rasmus Pagh, Nina Mesing Stausholm:
Infinitely Divisible Noise in the Low Privacy Regime. ALT 2022: 881-909 - Debarati Das, Barna Saha:
Approximating LCS and Alignment Distance over Multiple Sequences. APPROX/RANDOM 2022: 54:1-54:21 - Anders Aamand, Mikkel Abrahamsen, Thomas D. Ahle, Peter M. R. Rasmussen:
Tiling with Squares and Packing Dominos in Polynomial Time. SoCG 2022: 1:1-1:17 - Radu Curticapean:
Determinants from Homomorphisms. ESA 2022: 38:1-38:7 - Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, Barna Saha, Hamed Saleh:
Õ(n+poly(k))-time Algorithm for Bounded Tree Edit Distance. FOCS 2022: 686-697 - Aaron Bernstein, Danupon Nanongkai, Christian Wulff-Nilsen:
Negative-Weight Single-Source Shortest Paths in Near-linear Time. FOCS 2022: 600-611 - Radu Curticapean, Nutan Limaye, Srikanth Srinivasan:
On the VNP-Hardness of Some Monomial Symmetric Polynomials. FSTTCS 2022: 16:1-16:14 - Debarati Das, Tomasz Kociumaka, Barna Saha:
Improved Approximation Algorithms for Dyck Edit Distance and RNA Folding. ICALP 2022: 49:1-49:20 - Jakob Bæk Tejs Houen, Mikkel Thorup:
Understanding the Moments of Tabulation Hashing via Chaoses. ICALP 2022: 74:1-74:19 - Matti Karppa, Rasmus Pagh:
HyperLogLogLog: Cardinality Estimation With One Log More. KDD 2022: 753-761 - Aleksander B. G. Christiansen, Jacob Holm, Eva Rotenberg, Carsten Thomassen:
On Dynamic α + 1 Arboricity Decomposition and Out-Orientation. MFCS 2022: 34:1-34:15 - Anders Aamand, Justin Y. Chen, Piotr Indyk:
(Optimal) Online Bipartite Matching with Degree Information. NeurIPS 2022 - Anders Aamand, Justin Y. Chen, Piotr Indyk, Shyam Narayanan, Ronitt Rubinfeld, Nicholas Schiefer, Sandeep Silwal, Tal Wagner:
Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks. NeurIPS 2022